package 递归回溯.二维版;

public class JZ13机器人的运动范围 {

    /**
     * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
     * 一个机器人从坐标 [0, 0] 的格子开始移动，
     * 它每次可以向左、右、上、下移动一格（不能移动到方格外），
     * 也不能进入行坐标和列坐标的数位之和大于k的格子。
     * 例如，当k为18时，机器人能够进入方格 [35, 37] ，
     * 因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。
     * 请问该机器人能够到达多少个格子？
     *
     * 示例 1：
     * 输入：m = 2, n = 3, k = 1
     * 输出：3
     * 示例 2：
     * 输入：m = 3, n = 1, k = 0
     * 输出：1
     * 提示：
     * 1 <= n,m <= 100
     * 0 <= k <= 20
     */

    private boolean isAfter[][];
    private int k;
    private int[][] around={{-1,0},{0,1},{1,0},{0,-1}};
    private int count;

    public int movingCount(int m, int n, int k) {
        this.isAfter=new boolean[m][n];
        this.k=k;
        dfs(0,0);
        return count;
    }

    private void dfs(int x,int y){

        if(x>=isAfter.length||y>=isAfter[0].length||x<0||y<0){
            //越界
            return;
        }

        if(!isValid(x,y)||isAfter[x][y]){
            //未通过认证,或者已经走过了
            return;
        }

        isAfter[x][y]=true;
        count++;

        for (int i = 0; i < 4; i++) {
            //上右下左
            dfs(x+around[i][0],y+around[i][1]);
        }

    }

    private boolean isValid(int x,int y){
        String xStr=String.valueOf(x);
        String yStr=String.valueOf(y);
        int num=0;
        for (int i = 0; i < xStr.length(); i++) {
            num+=(xStr.charAt(i)-'0');
        }
        for (int i = 0; i < yStr.length(); i++) {
            num+=(yStr.charAt(i)-'0');
        }
        return num<=k;
    }

}
